Codeforces Round #31 (Div. 2)

A

弱智题，枚举即可。

Code

#include <cstdio>

const int N = 105;

int a[N], n;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                if (a[i] == a[j] + a[k] && j != k) {
                    printf("%d %d %d\n", i, j, k);
                    return 0;
                }
    }
    puts("-1");
}

B

字符串模拟题，讨论判断一下即可。

Code

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool check(string s) {
    if (s[0] == '@' || s[s.size() - 1] == '@') return false;
    int cnt = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '@') cnt++;
    }
    if (cnt == 0) return false;
    for (int i = 1; i < s.size() - 1; i++) {
        if (s[i - 1] == '@' && s[i + 1] == '@' || s[i] == '@' && s[i + 1] == '@') 
            return false;
    }
    return true;
}

int main() {
    string s;
    cin >> s;
    if (!check(s)) {
        puts("No solution");
        return 0;
    }
    while (s.size()) {
        int pos = s.find('@');
        cout << s.substr(0, pos + 2);
        s = s.substr(pos + 2);
        if (s.find('@') != -1) cout << ",";
    }
}

C

先按照左端点排序，枚举被删掉的课程，剩下的扫一遍判断是否有重叠即可。

时间复杂度 $O(n^2)$ 。

Code

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 5005;

struct Node {
    int l, r, id;
} p[N];

bool operator <(Node a, Node b) {
    return a.l < b.l || a.l == b.l && a.r < b.r;
}

int n, cnt, ans[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i].l, &p[i].r);
        p[i].id = i;
    }
    sort(p + 1, p + n + 1);
    p[0] = {0, 0};
    for (int i = 1; i <= n; i++) {
        int ok = 1;
        for (int j = 1; j <= n; j++) {
            if (j == i) continue;
            if (p[j].l < p[j - 1 - (j == i + 1)].r) ok = 0;
        }
        if (ok) cnt++, ans[cnt] = p[i].id;
    }
    sort(ans + 1, ans + cnt + 1);
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; i++) printf("%d%c", ans[i], " \n"[i == cnt]);
}

D

注意到切割出来每一块一定都是矩形，于是把每一条切割线转化为在被切开的方格之间按方向打上标记，爆搜记录连通块大小即可。

时间复杂度 $O(n\times\max\{w,h\}+wh)$ 。

Code

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 105;
const int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

int vis[N][N], f[N][N][4], ans[N * N], n, m, w, h, cnt;

void cut(int x1, int y1, int x2, int y2) {
    if (y1 == y2) {
        if (x1 > x2) swap(x1, x2);
        int j = y1;
        for (int i = x1; i < x2; i++) {
            f[i + 1][j][0] = 1;
            f[i + 1][j + 1][1] = 1;
        }
    }
    if (x1 == x2) {
        if (y1 > y2) swap(y1, y2);
        int i = x1;
        for (int j = y1; j < y2; j++) {
            f[i][j + 1][2] = 1;
            f[i + 1][j + 1][3] = 1;
        }
    }
}

bool in(int x, int y) {
    return 1 <= x && x <= w && 1 <= y && y <= h;
}

void dfs(int x, int y) {
    vis[x][y] = 1;
    cnt++;
    for (int dir = 0; dir < 4; dir++) {
        if (f[x][y][dir]) continue;
        int tx = x + d[dir][0];
        int ty = y + d[dir][1];
        if (!vis[tx][ty] && in(tx, ty)) dfs(tx, ty);
    }
}

int main() {
    scanf("%d%d%d", &w, &h, &n);
    for (int i = 1, x1, x2, y1, y2; i <= n; i++) {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        cut(x1, y1, x2, y2);
    }
    for (int i = 1; i <= w; i++)
        for (int j = 1; j <= h; j++)
            if (!vis[i][j]) {
                cnt = 0;
                dfs(i, j);
                ans[++m] = cnt;
            }
    sort(ans + 1, ans + m + 1);
    for (int i = 1; i <= m; i++) printf("%d%c", ans[i], " \n"[i == m]);
}

E

以下内容为照搬题解

直接暴力 $\binom{2n}{n}$ 肯定过不了，考虑dp 。

令 $f_{i,j}$ 为选择 $s$ 的前 $i$ 位，其中有 $j$ 位接到 $A$ 后面，其余接到 $B$ 后面的 $A+B$ 最大值。

但是这个东西需要考虑 $A$ 和 $B$ 分别为多少，没有办法转移，我们考虑从后往前推。

令 $f_{i,\,j}$ 为从第 $i$ 到 $2n$ 位中选择 $j$ 位接到 $A$ 后面，其余接到 $B$ 后面的 $A+B$ 最大值.

易知接到 $B$ 后面的数共 $k=2n-i-j+1$ 位，从而有

$f_{i,\,j}=\max\{f_{i,\,j},f_{i+1,\,j-1}+10^{j}\times s_i\}[j>0]$

$f_{i,\,j}=\max\{f_{i,\,j},f_{i+1,\,j}+10^{k}\times s_i\}[k>0]$

最后搜索判断决策点并输出方案，时间复杂度 $O(n^2)$ 。

注意需要开 unsigned long long 。

Code

#include <algorithm>
#include <cstdio>
using namespace std;

typedef unsigned long long uint64;

const int N = 50;

uint64 f[N][N], p[N], n;
char s[N];

void dfs(int i, int j) {
    if (i == 2 * n + 1) return;
    if (j && f[i][j] == f[i + 1][j - 1] + p[j] * (s[i] - '0'))
        putchar('H'), dfs(i + 1, j - 1);
    else
        putchar('M'), dfs(i + 1, j);
}

int main() {
    scanf("%d%s", &n, s + 1);
    p[0] = 1;
    for (int i = 1; i <= n * 2; i++) p[i] = p[i - 1] * 10;
    for (int i = n * 2; i >= 1; i--) {
        for (int j = 0; j + i - 1 <= n * 2; j++) {
            int k = n * 2 - (j + i - 1);
            if (j) f[i][j] = max(f[i][j], f[i + 1][j - 1] + p[j] * (s[i] - '0'));
            if (k) f[i][j] = max(f[i][j], f[i + 1][j] + p[k] * (s[i] - '0'));
        }
    }
    dfs(1, n);
}